import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Scanner;

/**
 * @author yu
 * @date 2025/6/4 15:18
 * @description: 131. 分割回文串
 * 给你一个字符串 s，请你将 s 分割成一些子串，
 * 使每个子串都是 回文串 。返回 s 所有可能的分割方案。
 * 【回文串 是正着读和反着读都一样的字符串。】
 * 示例 1：
 * 输入：s = "aab"
 * 输出：[["a","a","b"],["aa","b"]]
 * 示例 2：
 * 输入：s = "a"
 */
public class _07_backtracking_07_131 {
    /*static List<List<String>> res = new ArrayList<>();
    static List<String> cur = new ArrayList<>();

    public static List<List<String>> partition(String s) {
        backtracking(s, 0, new StringBuilder());
        return res;
    }

    private static void backtracking(String s, int start, StringBuilder sb){
        //因为是起始位置一个一个加的，所以结束时start一定等于s.length,因为进入backtracking时一定末尾也是回文，所以cur是满足条件的
        if (start == s.length()){
            //注意创建一个新的copy
            res.add(new ArrayList<>(cur));
            return;
        }
        //像前两题一样从前往后搜索，如果发现回文，进入backtracking,起始位置后移一位，循环结束照例移除cur的末位
        for (int i = start; i < s.length(); i++){
            sb.append(s.charAt(i));
            if (check(sb)){
                cur.add(sb.toString());
                backtracking(s, i + 1, new StringBuilder());
                cur.remove(cur.size() -1 );
            }
        }
    }

    //helper method, 检查是否是回文
    private static boolean check(StringBuilder sb){
        for (int i = 0; i < sb.length()/ 2; i++){
            if (sb.charAt(i) != sb.charAt(sb.length() - 1 - i)){return false;}
        }
        return true;
    }*/

    /* -------  回溯+动态规划优化回文串判断  ---------- */
    static List<List<String>> result;
    static LinkedList<String> path;
    static boolean[][] dp;

    static public List<List<String>> partition(String s) {
        result = new ArrayList<>();
        char[] str = s.toCharArray();
        path = new LinkedList<>();
        dp = new boolean[str.length + 1][str.length + 1];
        isPalindrome(str);
        backtracking(s, 0);
        return result;
    }

    public static void backtracking(String str, int startIndex) {
        if (startIndex >= str.length()) {
            //如果起始位置大于s的大小，说明找到了一组分割方案
            result.add(new ArrayList<>(path));
        } else {
            for (int i = startIndex; i < str.length(); ++i) {
                if (dp[startIndex][i]) {
                    //是回文子串，进入下一步递归
                    //先将当前子串保存入path
                    path.addLast(str.substring(startIndex, i + 1));
                    //起始位置后移，保证不重复
                    backtracking(str, i + 1);
                    path.pollLast();
                } /*else {
                    //不是回文子串，跳过
                    continue;
                }*/
            }
        }
    }

    //通过动态规划判断是否是回文串,参考动态规划篇 52 回文子串
    public static void isPalindrome(char[] str) {
        for (int i = 0; i <= str.length; ++i) {
            dp[i][i] = true;
        }
        for (int i = 1; i < str.length; ++i) {
            for (int j = i; j >= 0; --j) {
                if (str[j] == str[i]) {
                    if (i - j <= 1) {
                        dp[j][i] = true;
                    } else if (dp[j + 1][i - 1]) {
                        dp[j][i] = true;
                    }
                }
            }
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String s = scanner.nextLine();
        List<List<String>> result = partition(s);
        System.out.println(result);
    }
}
